//
// Created by Administrator on 2021/5/10.
//
#include <vector>
#include <iostream>

using namespace std;

class CustomStack {
private:
    int top; // 栈顶指针
    vector<int> stk{}; // 数组模拟栈
public:
    CustomStack(int maxSize) {
        stk.resize(maxSize);
        this->top = -1;
    }

    void push(int x) {
        if (top != stk.size() - 1) {
            stk[++top] = x;
        }
    }

    int pop() {
        if (top == -1) return -1;
        else {
            return stk[top--];
        }
    }

    void increment(int k, int val) {
        for (int i = 0; i < min(k, top + 1); ++i) {
            stk[i] += val;
        }
    }
};

class CustomStack2 { // inc操作优化
private:
    vector<int> stk, add; // 增加一个数组记录inc操作，只在pop的时候实际发生，而不是每个inc都对元素操作
    int top;
public:
    CustomStack2(int maxSize) {
        stk.resize(maxSize);
        add.resize(maxSize);
        top = -1;
    }

    void push(int x) {
        if (top != stk.size() - 1) {
            ++top;
            stk[top] = x;
        }
    }

    int pop() {
        if (top == -1) {
            return -1;
        }
        int ret = stk[top] + add[top];
        if (top != 0) {
            add[top - 1] += add[top]; // 传递增量信息
        }
        add[top] = 0;
        --top;
        return ret;
    }

    void increment(int k, int val) {
        int lim = min(k - 1, top);
        if (lim >= 0) {
            add[lim] += val;
        }
    }
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack* obj = new CustomStack(maxSize);
 * obj->push(x);
 * int param_2 = obj->pop();
 * obj->increment(k,val);
 */

int main() {
//    auto obj = new CustomStack(2);
//    obj->push(1);
//    obj->push(2);
//    cout << obj->pop() << endl;
//    obj->push(2);
//    obj->push(3);
//    obj->push(4);
//    obj->increment(5, 100);
//    obj->increment(2, 100);
//    cout << obj->pop() << endl;
//    cout << obj->pop() << endl;
//    cout << obj->pop() << endl;
//    cout << obj->pop() << endl;
//
//    delete obj;
    auto obj = new CustomStack2(2);
    obj->push(34);
    cout << obj->pop() << endl;
    obj->increment(8, 100);
    cout << obj->pop() << endl;
    obj->increment(9, 91);
    obj->push(63);
    cout << obj->pop() << endl;
    obj->push(84);
    obj->increment(10, 93);
    obj->increment(6, 45);
    obj->increment(10, 4);


    delete obj;
    return 0;
}